package demo1;

import java.util.Queue;
import java.util.Stack;
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node (int val) {
        this.val = val;
    }
}
public class Test {
    public static Node createTree () {
        Node node1 = new Node(4);
        Node node2 = new Node(2);
        Node node3 = new Node(5);
        Node node4 = new Node(1);
        Node node5 = new Node(3);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        return node1;
    }
    public static void main(String[] args) {
        Node node = createTree();
        treeToDoublyList(node);



    }
    public static Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        Node head = root;
        while (head.left != null && head.right != null) {
            head = head.left;
        }
        if (head != null) {
            while (head.right != null) {
                head = head.right;
            }
        }
        //inOrder(root);
        return head;
    }
}
